home *** CD-ROM | disk | FTP | other *** search
/ Best Tools for JAVA / Best Tools for JAVA.iso / JAVA_ALL / HOTJAVA_ / HOTJAVA / CLASSSRC / BROWSER / TOOLS / JAVASE~1 / SEARCH~1.JAV < prev    next >
Encoding:
Text File  |  1995-08-11  |  12.5 KB  |  391 lines
  1. /*
  2.  * @(#)Searcher.java    1.19 95/03/20 David A. Brown
  3.  *
  4.  * Copyright (c) 1994 Sun Microsystems, Inc. All Rights Reserved.
  5.  *
  6.  * Permission to use, copy, modify, and distribute this software
  7.  * and its documentation for NON-COMMERCIAL purposes and without
  8.  * fee is hereby granted provided that this copyright notice
  9.  * appears in all copies. Please refer to the file "copyright.html"
  10.  * for further important copyright and licensing information.
  11.  *
  12.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  13.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  14.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  15.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  16.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  17.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  18.  */
  19.  
  20. package browser.tools.JavaSearch;
  21.  
  22. import java.util.Vector;
  23. import java.util.Enumeration;
  24. import java.io.*;
  25.  
  26. /**
  27.  * Searcher:  Interface for *searching* a JavaSearch database.
  28.  *
  29.  */
  30. class Searcher {
  31.  
  32.     /** The database we're searching */
  33.     Database db;
  34.  
  35.     /** The window driving us, if any (for messages; can be null). */
  36.     SearchWindow searchWindow;
  37.  
  38.     /** The stop list, which we use to reject unimportant words. **/
  39.     StopList stopList;
  40.  
  41.     /** How many words we've read out of the index so far
  42.      *  doing the current search. */
  43.     int indexReadCounter;
  44.  
  45.     // Modes used internally by doSearch()
  46.     static final int  OR_MODE = 0;
  47.     static final int AND_MODE = 1;
  48.     static final int NOT_MODE = 2;
  49.  
  50.     /** Searcher constructor.  Specify a Database object and window. */
  51.     public Searcher(Database theDB, SearchWindow sWin) {
  52.     //System.out.println("Searcher [Database "+theDB.dbName+"]...");
  53.     db = theDB;
  54.     searchWindow = sWin;
  55.     stopList = new StopList(System.getenv("HOTJAVA_HOME")+File.separator+
  56.                 "doc"+File.separator+
  57.                 StopList.defaultFile);
  58.     }
  59.  
  60.     /** Searcher constructor.  Specify a Database object. */
  61.     public Searcher(Database theDB) {
  62.     this(theDB, null);
  63.     }
  64.  
  65.     /**
  66.      * Main "Search Engine" function, specifying a search string.
  67.      *
  68.      * Specify a search string, consisting of keywords to search for,
  69.      * along with optional boolean keywords "and", "or" and "not".
  70.      * Words must be separated by spaces!!
  71.  
  72.      * This method just breaks the search string into a Vector
  73.      * of search words, and calls doSearch(Vector searchWords)
  74.      * to do the actual searching.
  75.      *
  76.      * See below for details.
  77.      */
  78.     public DocList doSearch(String searchString) {
  79.     //System.out.println("doSearch:  searchString '"+searchString+"'...");
  80.     if ((searchString == null) || (searchString.length()==0)) {
  81.         return null;
  82.     }
  83.  
  84.     Vector wordVector = new Vector();
  85.     int wordStart = 0;
  86.     // Break apart searchString, adding keywords to wordVector.
  87.     while (wordStart<searchString.length()) {
  88.         // Skip over any spaces in searchString
  89.         while (searchString.charAt(wordStart) == ' ') {
  90.         wordStart++;
  91.         if (wordStart >= searchString.length()) break;
  92.         }
  93.         if (wordStart >= searchString.length()) break;
  94.         // Ok, wordStart really points to the start of a word.
  95.         int wordEnd = searchString.indexOf(' ',wordStart);
  96.         if (wordEnd == -1) wordEnd = searchString.length();
  97.         String keyword = searchString.substring(wordStart,wordEnd);
  98.         wordVector.addElement(keyword);
  99.         wordStart = wordEnd+1;
  100.     }
  101.     return doSearch(wordVector);
  102.     }
  103.  
  104.     
  105.     /**
  106.      * Main "Search Engine" function, specifying a Vector of
  107.      * search words.
  108.      *
  109.      * The searchWords parameter is a Vector of words representing
  110.      * a "search string" (ie. keywords to search for, mixed in with
  111.      * the optional boolean keywords "and", "or" and "not".)
  112.      *
  113.      * The search words are processed left to right
  114.      * (i.e. in the order they appear in the Vector), with any
  115.      * boolean keyword affecting how the *subsequent* word's
  116.      * hits are merged into the final result.  Note that
  117.      * "not" means "and not".
  118.      *
  119.      * Example: the Vector for "foo and bar or baz not mumble" is
  120.      * processed as follows:
  121.      *     - Find all documents containing "foo"
  122.      *     - INTERSECT this result with all documents containing "bar"
  123.      *     - Now ADD all documents containing "baz" to the result
  124.      *     - INTERSECT this result with all documents NOT
  125.      *           containing "mumble"
  126.      *
  127.      * Again, remember "not" means "and not".  This means
  128.      * that the results you get from searching for simply "not foo"
  129.      * might not be what you expect! 
  130.      *
  131.      * This method returns a DocList containing all documents
  132.      * which match the search string, in Doc ID order,
  133.      * or null if no documents match the search string.
  134.      */
  135.     public DocList doSearch(Vector searchWords) {
  136.  
  137.     //System.out.println("doSearch:  Number of searchWords: "+
  138.     //           searchWords.size()+"...");
  139.     //System.out.println("doSearch:  searchWords "+searchWords);
  140.  
  141.     // Start of with an empty set of Doc IDs
  142.     IDVector resultVector = new IDVector();
  143.  
  144.     // The query words we've dropped due to presence on stop list
  145.     Vector stoppedWords = new Vector(2);
  146.  
  147.     // The "boolean mode" to use when combining
  148.     //   our next set of Doc IDs with the
  149.     //   result set we're accumulating.
  150.     int booleanMode = OR_MODE; // OR is the default
  151.     
  152.     boolean onlyStopWords = true; // so far we've only seen stop words
  153.     Enumeration e = searchWords.elements();
  154.     while (e.hasMoreElements()) {
  155.         String keyword = (String)e.nextElement();
  156.  
  157.         // Make sure keyword is all lower-case
  158.         keyword = IndexingInputStream.downcase(keyword);
  159.         //System.out.println("doSearch:  processing keyword '"+keyword+"'.");
  160.  
  161.         // If the word is a boolean control keyword,
  162.         //   update booleanMode and continue
  163.         //   on to the next word
  164.         if (keyword.equals("or")) {
  165.         booleanMode = OR_MODE;
  166.         continue;
  167.         }
  168.         else if (keyword.equals("and")) {
  169.         booleanMode = AND_MODE;
  170.         continue;
  171.         }
  172.         else if (keyword.equals("not")) {
  173.         booleanMode = NOT_MODE;
  174.         continue;
  175.         }
  176.  
  177.         // Is it on our stop list?  If so, skip it.
  178.         if (stopList.isStopWord(keyword)) {
  179.         stoppedWords.addElement(keyword);
  180.         continue;
  181.         }
  182.  
  183.         // Ok, keyword is a real word.  Get an IDVector for it.
  184.         Word w = getWordFromIndex(keyword);
  185.         //System.out.println("doSearch:  getWordFromIndex returned: "+w);
  186.  
  187.         // Now we have a bunch of Doc IDs in w.idvector
  188.         //   (or, w may be null!)
  189.         // Merge that vector into resultVector, using
  190.         //   the current booleanMode:
  191.         switch (booleanMode) {
  192.         case AND_MODE:
  193.         if (w == null) {
  194.             // ANDing with a null set gives you a null set!
  195.             System.out.println("ANDing with a null set: clearing resultVector!");
  196.             resultVector.clear();
  197.         }
  198.         else {
  199.             // If we've only seen stopwords so far, don't bother to AND
  200.             // the null result with anything.
  201.             if (onlyStopWords) {
  202.             resultVector = w.idvector;
  203.             } else {
  204.             resultVector.intersectWith(w.idvector);
  205.             }
  206.         }
  207.         break;
  208.         case NOT_MODE:
  209.         if (w == null) {
  210.             // "AND NOT <null set>" doesn't change
  211.             //    what you started with.
  212.             //System.out.println("NOT with a null set; resultVector unaffected.");
  213.         }
  214.         else {
  215.             resultVector.intersectWithNot(w.idvector);
  216.         }
  217.         break;
  218.         default:        // OR mode
  219.                 if (w == null) {
  220.                     // "OR <null set>" doesn't change what you started with.
  221.             //System.out.println("OR with a null set; resultVector unaffected.");
  222.         }
  223.         else {
  224.             resultVector.unionWith(w.idvector);
  225.         }
  226.         break;
  227.         }
  228.  
  229.         // Reset booleanMode for the next word (we imply OR
  230.         //   if there's no boolean control keyword)
  231.         booleanMode = OR_MODE;
  232.  
  233.         // If we've gotten this far, we're seeing real words.
  234.         onlyStopWords = false;
  235.     }
  236.  
  237.  
  238.     // Done with the search!  Results are in resultVector.
  239.  
  240.     // Display stopped words, if any.
  241.     if (stoppedWords.size() > 0) {
  242.         if (searchWindow == null) {
  243.         System.out.print("Searcher: Discarded ");
  244.         for (int i = 0; i < stoppedWords.size(); i++) {
  245.             System.out.print(stoppedWords.elementAt(i)+" ");
  246.         }
  247.         System.out.print("\n");
  248.         } else {
  249.         searchWindow.displayStoppedWords(stoppedWords);
  250.         }
  251.     }
  252.     
  253.     if (resultVector.count == 0) {
  254.         //System.out.println("doSearch:  resultVector.count is 0!");
  255.         return null;
  256.     }
  257.  
  258.     //System.out.println("doSearch:  resultVector.count is "+
  259.     //           resultVector.count);
  260.  
  261.     // REMIND:  Would be cool to have a MAX_SEARCH_HITS paramater
  262.     //    here, so we don't create a DocList if we have an absurdly
  263.     //    large number of hits.
  264.     //
  265.     //    If (resultVector.count > MAX_SEARCH_HITS), we could either
  266.     //    truncate resultVector to an acceptable length,
  267.     //    or (better) return a special value indicating
  268.     //    we had too many hits (so the user should refine his
  269.     //    search, and try again...)
  270.     //
  271.     //    Actually, it would be cool for this method to
  272.     //    somehow return a number_of_hits *and* a DocList!
  273.     //    So if the DocList comes back null, the
  274.     //    number_of_hits tells you whether your got NO hits,
  275.     //    or too many hits.
  276.  
  277.     // Generate and return a new DocList based on resultVector --
  278.     //  this involves opening the .docs and .docindex files,
  279.     //  and reading a Doc object for each hit.
  280.     DocList dl = new DocList(db, resultVector);
  281.     return dl;
  282.     }
  283.  
  284.     /** Look up the specified word in the index, and return a
  285.      *  Word object.  Return null if the word wasn't found. */
  286.     public synchronized Word getWordFromIndex(String aWord) {
  287.     //System.out.println("getWordFromIndex:  finding '"+aWord+"'...");
  288.     indexReadCounter = 0;
  289.     
  290.     // Open the index and qindex files
  291.     RandomAccessFile indexFile =
  292.         new RandomAccessFile(db.indexFilename,"r");
  293.     RandomAccessFile qindexFile =
  294.         new RandomAccessFile(db.qindexFilename,"r");
  295.  
  296.     int numWords = qindexFile.length()/4;
  297.     //System.out.println("getWordFromIndex:  qindexFile has "+
  298.     //           numWords+" entries.");
  299.  
  300.  
  301.     // Binary search the qindex file (each qindex
  302.     //   entry points at a word in the index file)
  303.     Word resultWord = bsearchWord(aWord,
  304.                       0, numWords-1,
  305.                       qindexFile, indexFile);
  306.     //System.out.println("getWordFromIndex:  Got resultWord: "+resultWord);
  307.     //System.out.println("   Did "+indexReadCounter+" read"+
  308.     //           ((indexReadCounter==1)?"":"s")+
  309.     //           " from the index/qindex files.");
  310.     return resultWord;
  311.     }
  312.  
  313.     //
  314.     // These methods are the guts of the getWordFromIndex() functionality
  315.     //
  316.  
  317.     /**
  318.      * Binary-search index file for the specified word.
  319.      * Returns a Word object if the word is found;
  320.      * Returns null if the word is not in the index.
  321.      * Calls itself recursively.
  322.      */
  323.     private Word bsearchWord(String word, int loPos, int hiPos,
  324.                  RandomAccessFile qindexFile,
  325.                  RandomAccessFile indexFile) {
  326.  
  327.     //System.out.println("  bsearchWord ("+word+"), range ["+
  328.     //           loPos+","+hiPos+"]...");
  329.  
  330.     if (loPos > hiPos) {
  331.         //System.out.println("  loPos > hiPos.  ["+loPos+","+hiPos+"].  Returning null.");
  332.         return null;
  333.     }
  334.     else if (loPos == hiPos) {
  335.         if (word.equals(getWordAtPos(loPos, qindexFile, indexFile))) {
  336.         return new Word(word,indexFile);
  337.         }
  338.         else {
  339.         return null;
  340.         }
  341.     }
  342.     else {
  343.         // loPos and hiPos describe a range.  Check the
  344.         //   *middle* of the range, and recurse.
  345.         int midPos = (loPos+hiPos)/2;
  346.         String midWord = getWordAtPos(midPos, qindexFile, indexFile);
  347.         //System.out.println("    midPos "+midPos+
  348.         //           ", midWord '"+midWord+"'.");
  349.         int compareResult = word.compareTo(midWord);
  350.         if (compareResult == 0) {
  351.         // Direct hit!
  352.         return new Word(word,indexFile);
  353.         }
  354.         else if (compareResult < 0) {
  355.         // word < midWord:  Search the lower half
  356.         return bsearchWord(word, loPos, midPos-1,
  357.                    qindexFile, indexFile);
  358.         }
  359.         else {
  360.         // word > midWord:  Search the upper half
  361.         return bsearchWord(word, midPos+1, hiPos,
  362.                    qindexFile, indexFile);
  363.         }
  364.     }
  365.     }
  366.  
  367.     /** Return the word found at the Nth position in the index file.
  368.      *  Leaves indexFile pointing at the word's doc entries. */
  369.     private String getWordAtPos(int n, RandomAccessFile qindexFile,
  370.                 RandomAccessFile indexFile) {
  371.     //System.out.print("    getWordAtPos "+n+"...  ");
  372.  
  373.     // Read an index file position from the qindex file.
  374.     // qindex entries are ints, which are 4 bytes long.
  375.     qindexFile.seek(n*4);
  376.     int indexPos = qindexFile.readInt();
  377.  
  378.     // Read just the word (a String) from the index file
  379.     indexFile.seek(indexPos);
  380.     String word = indexFile.readLine();
  381.     //System.out.println("found word '"+word+"'.");
  382.  
  383.     indexReadCounter++;    // One indexReadCounter increment
  384.                 //   means one int from the qindexFile
  385.                 //   and one String from the indexFile.
  386.  
  387.     return word;
  388.     }
  389.  
  390. }
  391.